package leecode

import "sort"

func permuteUnique(nums []int) (result [][]int) {
	sort.Ints(nums)
	path := make([]int, 0, len(nums))
	var backtracking func(used1 []bool, used2 []bool)
	used1, used2 := make([]bool, len(nums)), make([]bool, len(nums))
	backtracking = func(used1 []bool, used2 []bool) {
		if len(path) == len(nums) {
			temp := make([]int, len(path))
			copy(temp, path)
			result = append(result, temp)
			return
		}
		for i := 0; i < len(nums); i++ {
			if i > 0 && nums[i] == nums[i-1] && used2[i-1] == false {
				continue
			}
			if used1[i] == true {
				continue
			}
			used1[i] = true
			used2[i] = true
			path = append(path, nums[i])
			backtracking(used1, used2)
			used1[i] = false
			used2[i] = false
			path = path[:len(path)-1]
		}
	}
	backtracking(used1, used2)
	used1 = append(used1, false) //判断树枝元素是否重复
	used2 = append(used2, false) //判断同一层使用的元素是否重复
	return
}
